package arithmetic.baseAlgorithm.sort;

/**
 * 归并排序
 * 从小到大
 *
 * @author zhangyanqi
 * @since 1.0 2018/1/3
 */
public class MergeSort {


    private static void sort(int[] toSort, int begin, int end) {
        //左边排序，右边排序，然后合并
        int mid = (end - begin) / 2 + begin;
        if (begin >= end || mid == 0) {
            return;
        }
        sort(toSort, begin, mid);
        sort(toSort, mid + 1, end);
        merge(toSort, begin, mid, end);
    }

    /**
     * 将一个数组的指定的2个部分重新排序
     *
     * @param array
     * @param begin
     * @param mid
     * @param end
     */
    private static void merge(int[] array, int begin, int mid, int end) {
        if (begin == end || begin == mid) {
            return;
        }
        int length = mid - begin;
        int[] array1 = new int[length];
        int[] array2 = new int[length];
        System.arraycopy(array, begin, array1, 0, length);
        System.arraycopy(array, mid, array2, 0, length);
        int i = 0, j = 0;
        for (int a = begin; a < end; a++) {
            if (j < length && ( i >= length ||array1[i] > array2[j])) {
                array[a] = array2[j++];
            } else if (i < length) {
                array[a] = array1[i++];
            }
        }
    }

    public static void main(String[] args) {
        int[] ints = {3, 2, 1, 5, 7, 6};
        sort(ints, 0, ints.length - 1);
        System.out.println(ints[0] + " " + ints[1] + " " + ints[2] + " " + ints[3] + " " + ints[4] + " " + ints[5]);
    }
}
